//<p>给你一个整数数组 <code>nums</code>，有一个大小为&nbsp;<code>k</code><em>&nbsp;</em>的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 <code>k</code>&nbsp;个数字。滑动窗口每次只向右移动一位。</p>
//
//<p>返回 <em>滑动窗口中的最大值 </em>。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<b>输入：</b>nums = [1,3,-1,-3,5,3,6,7], k = 3
//<b>输出：</b>[3,3,5,5,6,7]
//<b>解释：</b>
//滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       <strong>3</strong>
// 1 [3  -1  -3] 5  3  6  7       <strong>3</strong>
// 1  3 [-1  -3  5] 3  6  7      <strong> 5</strong>
// 1  3  -1 [-3  5  3] 6  7       <strong>5</strong>
// 1  3  -1  -3 [5  3  6] 7       <strong>6</strong>
// 1  3  -1  -3  5 [3  6  7]      <strong>7</strong>
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<b>输入：</b>nums = [1], k = 1
//<b>输出：</b>[1]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><b>提示：</b></p>
//
//<ul> 
// <li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li> 
// <li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li> 
// <li><code>1 &lt;= k &lt;= nums.length</code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>队列</li><li>数组</li><li>滑动窗口</li><li>单调队列</li><li>堆（优先队列）</li></div></div><br><div><li>👍 1843</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.LinkedList;

/**
 * 滑动窗口最大值
 * @author DY Rising
 * @date 2022-09-06 20:48:52
 */
public class P239_SlidingWindowMaximum{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P239_SlidingWindowMaximum().new Solution();
        LinkedList<Integer> queue = new LinkedList();
        queue.add(0);
        queue.add(10);
        queue.add(2);
        queue.add(3);

        System.out.println(queue.peek());
        System.out.println(queue.peekLast());
        System.out.println(queue.peekFirst());
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k) {
            return nums;
        }
        //存放结果
        int[] result = new int[nums.length - k + 1];
        //利用双端队列保存一个有序队列，从大到小排列，其中队头即是最大值
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //从队尾取出数据，然后和当前值进行比较，若是比当前值小，直接弹出队尾元素
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            //经历完上一步，队列中都是比当前元素大的，然后将当前元素添加
            queue.addLast(i);
            //判断队首元素是否在滑动窗口内
            if (queue.peekFirst() <= i - k) {
                //已经不在滑动窗口内，直接移除
                queue.pollFirst();
            }
            if (i - k + 1 >= 0) {
                result[i - k + 1] = nums[queue.peekFirst()];
            }

        }

        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
